package LeetCodeHot100TopInterview;

public class Q142_CircleLink2 {
    //环形链表 2
    //返回链表的入环点
    //上一问 Q141 判断是否有环 追击相遇只是判断是否成环 无法定位到入环节点
    //这个原理就不太好解释了
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null){
            return null;
        }
        ListNode Insec = hasCycle(head);
        if (Insec == null){
            return null;
        }
        while (head != Insec){
            head = head.next;
            Insec = Insec.next;
        }
        return head;
    }

    //环形链表 ==> 判断是否有环 ==> 改:返回相交点 且快慢应遵循同一起点
    //解释原理很简单 ==> 绕圈圈 追及必定相遇
    //腾讯
    public ListNode hasCycle(ListNode head) {
        if (head == null || head.next == null){
            return null;
        }
        //快慢指针
        ListNode slow = head;
        ListNode fast = head;
        do {
            if (slow == null || fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);

        return slow;
    }


    public static void main(String[] args) {
        Q142_CircleLink2 fun = new Q142_CircleLink2();
        ListNode node = new ListNode(3);
        node.next = new ListNode(2);
        node.next.next = new ListNode(0);
        node.next.next.next = new ListNode(-4);
        node.next.next.next.next = node.next;
        System.out.println(fun.detectCycle(node).val);
    }
}
